package algorithms.que13;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

import java.util.Iterator;

/**
 * @功能
 * @创建时间 2020/7/12
 */
public class RandomBag1<Item> implements Iterable<Item> {

    /**
     * @param args
     */
    private Item[] a = (Item[]) new Object[1];
    private int N = 0;
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    private void resize(int length){
        Item[] temp = (Item[]) new Object[length];
        for(int i=0;i<N;i++){
            temp[i] = a[i];
        }
        a = temp;
    }
    public void add(Item item){
        if(N == a.length) resize(2*a.length);
        a[N++] = item;
    }

    @Override
    public Iterator<Item> iterator() {
        // TODO Auto-generated method stub
        return new RandomBagIterator();
    }
    private class RandomBagIterator implements Iterator<Item>{

        private int[] seq = new int[N];
        private int cur = 0;
        public RandomBagIterator(){
            for(int i=0;i<seq.length;i++)
                seq[i] = i;
            StdRandom.shuffle(seq);
        }
        @Override
        public boolean hasNext() {
            // TODO Auto-generated method stub
            return cur != seq.length;
        }

        @Override
        public Item next() {
            // TODO Auto-generated method stub
            return a[seq[cur++]];
        }

        @Override
        public void remove() {
            // TODO Auto-generated method stub

        }

    }
    public static void main(String[] args) {
        RandomBag<Integer> r = new RandomBag<Integer>();
        int[] cnt = new int[4];
        for(int i=0;i<4;i++)
            r.add(i);
        for(int i=0;i<100000;i++){
            Iterator<Integer> it = r.iterator();
            cnt[it.next()]++;
        }
        for(int i=0;i<cnt.length;i++)
            StdOut.println(i + " " + (double)cnt[i]/100000);
    }




}

